from tabnanny import verbose


""" 正则表达式匹配
状态转移方程
dp[i][j] = /
           | if p[j] != '*' --> / dp[i-1][j-1]  s[i]==p[j] or p[j]=='.'
           |                    \ False         otherwise
           | otherwise      --> / dp[i-1][j] or dp[i][j-2]  s[i]==p[j-1] or p[j-1]=='.'
           \                    \ dp[i][j-2]                otherwise

"""
class Solution:
    def isMatch(self, s: str, p: str, verbose: bool) -> bool:
        m = len(s)
        n = len(p)
        table = [[False] * (n+1) for _ in range(m+1)]
        table[0][0] = True

        for j in range(1, n+1):
            if p[j-1] == '*':
                table[0][j] = (table[0][j-1] or table[0][j-2])

        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == p[j-1] or p[j-1] == '.':
                    table[i][j] = table[i-1][j-1]
                elif p[j-1] == '*':  # 前面必有有效字符
                    if s[i-1]==p[j-2] or p[j-2] == '.':
                        table[i][j] = table[i-1][j] or table[i][j-2]
                    else:  # 跳过当前 字母+* 组合
                        table[i][j] = table[i][j-2]
                    
        if verbose:
            for i in range(0, m+1):
                print(table[i])
        
        return table[m][n]
    

if __name__ == "__main__":
    so = Solution()
    
    # print(so.isMatch('n', '.*', verbose=False))
    # print(so.isMatch('n', '..*', verbose=False))
    # print(so.isMatch('n', '...*', verbose=False))
    print(so.isMatch('m', 'm*.', verbose=True))
    # print(so.isMatch('abzsdfgbnjn', '......g.*', verbose=False))
    print(so.isMatch('ssip', 's*p*', verbose=True))
    print(so.isMatch('s', 's*p*', verbose=True))
    print(so.isMatch('aaa', 'ab*a*c*a', verbose=True))
